﻿//1930. 长度为 3 的不同回文子序列
//给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。
//即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。
//回文 是正着读和反着读一样的字符串。
//子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。
//例如，"ace" 是 "abcde" 的一个子序列。


class Solution {
public:
    int countPalindromicSubsequence(string s)
    {
        int n = s.size();
        vector<int> suf(n);
        int x = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            x |= 1 << (s[i] - 'a');
            suf[i] = x;
        }
        int prev = 0;
        prev |= 1 << (s[0] - 'a');
        bool cnt[26][26];
        int ans = 0;
        for (int i = 1; i < n - 1; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                if ((suf[i + 1] >> j) & 1 && (prev >> j) & 1)
                {
                    if (!cnt[s[i] - 'a'][j])
                    {
                        ans++;
                        cnt[s[i] - 'a'][j] = true;
                    }
                }
            }
            prev |= 1 << (s[i] - 'a');
        }
        return ans;
    }
};